\input macros
%\input patch
\tolerance=2500
\def\bookline{\CLOS\  Specification}
\def\chapline{Programmer Interface Concepts}

\beginChapter 1.{Common Lisp Object System Specification}%
{Programmer Interface Concepts}{Programmer Interface Concepts}

Contributors to this document include Daniel G. Bobrow, Linda G.
DeMichiel,\break Richard P. Gabriel, Kenneth Kahn, Sonya E. Keene,
Gregor Kiczales, Larry\break Masinter, David A. Moon, Mark Stefik, and
Daniel L. Weinreb.

Comments and suggestions on this document are encouraged.
Changes will be incorporated over the next several months.
This text will be made available to the X3J13 Committee for the
Common Lisp Standards effort.

\endTitlePage

\beginSection{Introduction}

This proposal presents a description of the standard Programmer
Interface for object-oriented programming in the \CLOS.    The first
chapter of this document describes the concepts of the \CLOS, and the
second gives an alphabetic list of functions and macros that comprise
the \CLOS\ Programmer Interface.

A second document, ``The \CLOS\ Meta-Object Protocol,'' will describe how the
\CLOS\ can be customized to support other existing object-oriented
paradigms and to define new ones.

The fundamental objects of the \CLOS\ are classes, instances,
generic functions, and methods. 

A {\bit class\/} object determines the structure and behavior of a set
of other objects, called its {\bit instances}.  It is an important
feature of the \OS\ that every Common Lisp object is an {\bit
instance\/} of a class.  The class of an object determines the set of
operations that can be performed on the object.

A {\bit generic function} is a function whose behavior depends on the
classes or identities of the arguments supplied to it.  A generic function object
comprises a set of {\bit methods\/}, a lambda-list, a method-combination type,
and possibly some options.   The methods define the  
class-specific behavior and operations of the generic function.  
Thus, generic functions are objects that may be {\bit specialized} by the 
definition of methods to provide class-specific operations.  A generic
function chooses one or more of the set of its methods based on the
classes of its arguments.   

A generic function can be used in 
the same ways that an ordinary function can be used in Common Lisp; in
particular, a generic function can be used as an argument to {\bf
funcall} and {\bf apply}.  Generic functions are named in the same way 
that ordinary functions are named; that is, the generic function 
object can be stored as the function definition of a symbol. 
%The naming conventions for generic functions are 
%precisely the same as those for ordinary Common Lisp functions. 

The class-specific operations provided by generic functions are
themselves defined and implemented by {\bit methods}.  
%Removed according to Moon's message of 1/25/87    -Sonya
%A method---also
%called a {\bit method object}---is a function that can be used in any
%of the ways that ordinary functions can be used in Common Lisp.  
A method object contains a method function, a set of {\bit parameter
specializers\/} that specify when the given method is applicable, and 
a set of {\bit qualifiers\/} that are used by the method combination to 
distinguish among methods.  
Each required formal parameter of each method has an associated
parameter specializer, and the method is expected to be invoked only
on arguments that satisfy its parameter specializers.

To summarize, a generic function is a function that contains or
encompasses a number of methods.  
%Removed this sentence.   Awkward and doesn't add anything.  -Sonya 
%The purpose of the generic function
%is to provide the object that contains all methods that provide the 
%pieces of code that define the behavior of the generic function.  
When a generic function is invoked, the classes of its required arguments
determine which methods might be invoked.  The behavior of the generic
function results from which methods are selected for execution, the
order in which the selected methods are called, and how their values
are combined to produce the value or values for the generic function.
The {\bit method combination\/} facility controls the selection of
methods, the order in which they are run, and the values that are
returned by the generic function.  The \CLOS\ offers a default method
combination type that is appropriate for most user programs.  The
\CLOS\ also provides a facility for declaring new types of method
combination for programs that require them.

\vfill
\endSection%{Introduction}

\beginSection{Classes}

A {\bit class\/} is an object that determines the structure and behavior 
of a set of other objects, called its {\bit instances}.   

A class can include other classes by reference in its definition, in order to inherit 
structure and behavior from those classes.  The newly defined class is
called a {\bit subclass\/} of each of the classes that it includes.  Each
of the included classes is called a {\bit superclass\/} of the 
newly defined class.

In situations where it matters whether a class is a direct superclass
or subclass of another, we use the following terminology.  We
say that a class, $C\sub{1}$, is a {\bit direct superclass\/} of 
a class, $C\sub{2}$, if $C\sub{2}$ includes 
$C\sub{1}$ as a superclass by explicit reference in its definition. 
We say that $C\sub{2}$ is a {\bit direct subclass\/} of $C\sub{1}$.  
We will say that a class 
$C\sub{n}$ is a {\bit superclass\/} of a class $C\sub{1}$ if there
exists a series of classes $C\sub{2},\ldots,C\sub{n-1}$ such that
$C\sub{i+1}$ is a direct superclass of $C\sub{i}$, for $1 \leq i<n$.
In this case, we say that $C\sub{1}$ is a {\bit subclass\/} of
$C\sub{n}$.  A class is considered neither a superclass nor a subclass of itself.  That 
is, if $C\sub{1}$ is a superclass of $C\sub{2}$, then $C\sub{1} \neq
C\sub{2}$.  We refer to the set of classes consisting of some given
class $C$ along with all of its superclasses as ``$C$ and its superclasses.''

When a class is defined, the order in which its direct superclasses
are mentioned in the defining form is important.  Each class has a
{\bit local precedence order\/}, which is a list consisting of the
class, followed by its direct superclasses in the order mentioned
in the defining form, followed by the class {\bf t}.

Each class has a {\bit class precedence list}, which is a total order on
the set of the given class and its superclasses.  The total order is
expressed as a list ordered from most specific to least specific.  The
class precedence list is used in several ways.  In general, more
specific classes override or alter features inherited from less specific
classes.  The method selection and combination process uses the class
precedence list to order methods from most specific to least specific.
A more specific class can override some of the options declared in the
{\bf defclass} form of a less specific class.
 
A class precedence list is always consistent with the local precedence
order of each class in the list.  The classes in each local precedence
order appear within the class precedence list in the same order.  If
the local precedence orders are inconsistent with each other, no class
precedence list can be constructed, and an error will be signalled.
The class precedence list and its computation is discussed at
length in the section ``Determining the Class Precedence List''.

%When a class that includes a set of direct superclasses is defined,
%the order in which those direct superclasses are mentioned in the
%defining form helps determine a total order on the classes at or above
%the newly defined class.  The order of the direct superclasses in the
%defining form is called the {\bit local precedence order\/} and is
%discussed below.

%Classes are organized into a {\bit lattice}, which gives them a
%partial order called the lattice order.  The top of the lattice is the
%class named {\bf t} and the bottom is the class named {\bf nil}.  The
%lattice order along with the local precedence order mentioned above
%can usually be combined to produce a third partial order that can be
%embedded in a total order on the classes at or above a given class.
%When the lattice and the local precedence order are inconsistent, they
%cannot be combined to produce a partial order.  The {\bit class precedence list}
%of a class is a list of the classes at or above that class, which are 
%arranged according to the total order.  When, for a given class, a
%total order on the classes at or above a given class cannot be
%determined, an error will be signalled during the normal operations of
%the \CLOS.  We will normally consider as well-defined only those class
%lattices with class precedence lists defined at every class except the
%class named {\bf nil}.  The class precedence and its computation will
%be discussed at length below.

There is a mapping from the Common Lisp type lattice
into the Common Lisp Object System class lattice.  Many of the standard 
Common Lisp types specified in {\it Common Lisp: The Language\/} by Guy
L. Steele Jr.  have a corresponding class, which has the same name as the 
type.  Some Common Lisp types do  
not have a corresponding class.   The integration of the type and class 
system is discussed later in this chapter.    

Classes are represented by first-class objects, which are themselves 
instances of classes.
The class of the class of an object is termed the {\bit metaclass\/}
of that object.  When no misinterpretation is possible, we will also
use the term {\bit metaclass\/} to refer to a class that has instances
that are themselves classes.  The metaclass determines the form of
inheritance used by the classes that are its instances and the
representation of the instances of those classes.  The \CLOS\ provides
a default metaclass that is appropriate for most programs.  The
meta-object protocol allows for defining and using new metaclasses.


%I removed this text for a couple reasons.   -Sonya 
%First, it's very confusing and doesn't belong so early in the
%introduction.
%Second, I hope we can improve the terminology. 

%The \CLOS\ includes a set of standard objects.  We use the term 
%{\bit standard object\/} to refer to any object whose metaclass is 
%{\bf class}.  The class {\bf object} specifies the default behavior of the
%set of all objects whose metaclass is {\bf class}.  In other words,
%all standard objects inherit (directly or indirectly) from the class
%{\bf object}. 
%
%The \CLOS\ also defines a set of standard classes.  A {\bit standard
%class\/} is any class that is an instance of the class {\bf class}.
%The class {\bf class} is itself of class {\bf class}.  It is therefore
%both a standard class and a standard object.  The class {\bf object}
%is also a standard class since it is also an instance of the class
%{\bf class}.  As a standard object, the class {\bf class} is a
%subclass of the class {\bf object}.
%
%\vfill\eject
%\Vskip 1pc!
%\boxfig
%{\bf\tabskip 0pt plus 1fil
%\halign to \hsize{&#\hfil\cr
%array&hashtable&sequence\cr
%atom*&integer&short-float\cr
%bignum&keyword&simple-array\cr
%bit&list&simple-bit-vector\cr
%bit-vector&long-float&simple-string\cr
%character&nil&simple-vector\cr
%common*&null&single-float\cr
%compiled-function&number&standard-char\cr
%complex&package&stream\cr
%cons&pathname&string\cr
%double-float&random-state&string-char\cr
%fixnum&ratio&symbol\cr
%float&rational&t\cr
%function&readtable&vector\cr
%}}
%\caption{Standard Common Lisp types.  All these types except atom and common have\break
%a corresponding class, which has the same name as the type.}
%\endfig

\beginsubSection{Defining Classes}

The macro {\bf defclass} is used to define a new class.  The syntax for 
{\bf defclass} is given in Figure~2-1.   

The definition of a class includes:

\beginlist

\item{\bull} The name of the new class.

\item{\bull} The list of direct superclasses of the new class. 

\item{\bull} A set of slot specifiers.  Each slot specifier includes the name of the  
slot and zero or more slot options.  A slot option pertains only to a
single slot.

\item{\bull} A set of class options.  Each class option pertains 
to the class as a whole.  
\endlist

The slot options and class options of the {\bf defclass} form allow for 
the following:

\beginlist

\item{\bull} Providing a default initial value form for one or more
slots.  
%pending initialization protocol -Sonya 
%When an instance is created it is possible to override this
%default initial value form; however, if not overridden, the default
%initial value form is evaluated to produce a value that is given to that
%slot.

\item{\bull} Requesting that methods for appropriately named generic functions
be automatically generated for reading or writing one or more slots. 

\item{\bull} Controlling whether one copy of a given slot is
shared by all instances or each instance has its own copy of that
slot.  

\item{\bull} Requesting that a constructor function be automatically
generated for making instances of this class.

\item{\bull} Indicating that the instances of this class are to have a
metaclass other than the default.
\endlist 

\beginsubSection{Creating Instances of Classes}

The function {\bf make-instance} creates and returns a new instance of a
class.   If the {\bf defclass} form indicates that some of the slots are
initializable, {\bf make-instance} accepts arguments specifying the slots to
initialize and the initial values.    

The initialization protocol is not yet specified. 

\endsubSection%{Creating Instances of Classes}

\beginsubSection{Slots}

Classes have named slots.  The name of a slot is a symbol, with the same
restrictions as variable names in {\bf let}.   
Each name can have a value associated with it.  The
scope of that association depends on the {\bf :allocation} slot option.

In general, slots are inherited by subclasses.   That is, slots defined in 
a class are usually also slots in any subclass of that class.  
A more specific class can override some of the slot options declared in the 
{\bf defclass} form of a less specific class, by providing a local description 
of the slot.   A detailed explanation of how slot options are inherited is given 
in the section ``Inheritance''.  

There are two kinds of slots.  The {\bf :allocation} slot option 
specifies whether the  
slot is an {\bf :instance} slot or a {\bf :class} slot.   
An {\bf :instance} slot is a place where 
data is stored in an instance.  This is the most commonly used 
kind of slot---each instance has an individual slot of the same 
name.  A {\bf :class} slot is a place where data is stored in a 
class.  There is only one slot, whose value is shared by all instances 
of the class.   Subclasses share the same {\bf :class} slot, unless  
a local slot description is given to override the sharing of this slot. 

\endsubSection%{Slots}

\beginsubSection{Accessing Slots}

Slots can be accessed in two ways: by use of the accessors defined in  
the {\bf defclass} form and by use of the primitive function 
{\bf slot-value}.   

The {\bf defclass} syntax allows for generating generic functions for
readers and accessors---these can be specified for individual slots or for
all slots. When a reader or accessor is specified for an individual slot,
the name of the generic function is directly specified.  When readers and
accessors are requested for all slots, the names of the generic functions
are determined by combining a prefix and the individual slot names.  If an 
accessor is requested, a method is automatically generated for reading the
value of the slot, and a {\bf setf} method for it is also generated.  If
a reader is requested, a method is automatically generated for reading the
value of the slot, but no {\bf setf} method for it is generated.  
These methods are added to the appropriate generic functions; the 
generic functions are implemented using {\bf slot-value}.   It is possible to 
modify the behavior of these generic functions by writing methods for 
them.  

The function {\bf slot-value} can be used with any of the slot names 
specified in the {\bf defclass} form to access a specific slot in an
object of the given class.  If the object has no such slot, an error is 
signalled.   Note that {\bf slot-value} can be used to read or write the
value of a slot whether or not the {\bf defclass} form specified
any accessor functions for that slot.   When
{\bf slot-value} is used, no methods for the accessors are called.

Sometimes it is convenient to access slots from within the body of a method
or function.  The macro {\bf with-slots} can be used to set up a lexical
environment in which certain slots are lexically available.   {\bf
with-slots} enables one to specify whether the accessors or {\bf
slot-value} should be used to access the slots.

\endsubSection%{Accessing Slots}
\endSection%{Classes}

\beginSection{Inheritance}

Inheritance is the key to program modularity within the \CLOS.  A typical
object-oriented program consists of several classes, each of which
defines some aspect of behavior.  New classes are defined by including
the appropriate classes as superclasses, thus gathering desired aspects
of behavior into one class.

A class inherits slots and some {\bf defclass} options from all of 
its superclasses.  This section describes what
is inherited from superclasses, and how a class can override an aspect
of inherited behavior.  
 
\beginsubSection{Inheritance of Methods}

A subclass inherits methods in the sense that any method
applicable to an instance of a class is also applicable to instances of
any subclass (all other arguments to the method being the same).  For
methods that have only one specialized argument, such as the 
accessors of a class, we say that subclasses inherit the use of those 
methods from the super class.

The inheritance of methods acts the same way regardless of whether the 
method was created using {\bf defmethod} or by using one of the {\bf defclass} 
options that cause methods to be generated automatically (for reading or 
writing the value of a slot). 

The inheritance of methods is described in detail in the section
``Method Selection and Combination.''   

\endsubSection%{Inheritance of Methods}

\beginsubSection{Inheritance of Slots and Slot Options}

In general, slot descriptions are inherited by subclasses.  That is,
slots defined in a class are usually also slots in any subclass of that
class.   One important rule is that an instance has at most one slot by
any given name accessible to it.

In the simplest case, only one class in the class precedence list
provides a slot description with a given slot name.  If it is an 
{\bf :instance} slot, then each instance of the class and all of its
subclasses allocate storage for it.  If it is a {\bf :class} slot, the
allocation of the slot is done by the class that provided the
slot-description, and the single slot is accessible by instances of
that class and all of its subclasses.

More than one class in the class precedence list can provide a slot 
description with a given slot name.  In such cases, at most one slot 
with a given name is accessible to any instance, and  
the characteristics of that slot involve some combination of the several  
slot descriptions.  The slot 
options provided by the various slot descriptions combine as follows:  

{\bf :allocation} comes from the most specific slot description in
the class precedence list---if it 
does not explicitly specify {\bf :allocation}, the default is 
{\bf :allocation} {\bf :instance}.   

{\bf :initform} comes from the most specific slot description 
that explicitly specifies {\bf :initform}.  
 
{\bf :type} is constrained to satisfy all of the type constraints given
by classes in the class precedence list.  That is, if T1, T2 and so on
are the type constraints given by the class and all of its superclasses,
the value of the slot must satisfy 
{\bf (typep value '(and T1 T2 T3...)}.  
This inheritance behavior allows a compiler to optimize on the
basis of the {\bf :type} option in the {\bf defclass} form.   Some
operations can be improved, e.g., when the slot is directly involved in
an arithmetic expression, such as being able to emit the machine
addition instruction with only overflow checking. 
%Does this signal an error or what, if the type is wrong?   

{\bf :reader} and {\bf :accessor} create methods at {\bf defclass} time,
and these methods are applicable, but the slot options themselves are
not inherited.

A superclass might allocate storage for a slot, and a subclass specify
{\bf :allocation} {\bf :none} for that slot.   This means that instances
of the subclass are not permitted to access the slot.   However, if {\bf
with-slots} is used on an instance of the subclass, {\bf with-slots}
does create a lexically apparent variable for this slot. 

Methods that access slots know only the name of the slot and the type
constraint on the slot's value.   Suppose a superclass provides a method, 
expecting to access a {\bf :class} slot of a given name.  
A subclass provides a local description of an {\bf :instance} 
slot with the same name.   If the 
method provided by the superclass is used on an instance of the subclass, 
the method accesses the {\bf :instance} slot. 

\endsubSection%{Inheritance of Slots and Slot Options}

\beginsubSection{Inheritance of Class Options}

{\bf :reader-prefix} and {\bf :accessor-prefix} create methods at {\bf defclass} time,
and these methods are applicable, but the class options themselves are
not inherited.

{\bf :constructor}, {\bf :documentation}, and {\bf :metaclass} 
are not inherited, and have no effect on subclasses. 

\endsubSection%{Inheritance of Class Options}

\beginsubSection{Examples of Inheritance}

\screen!

(defclass C1 () ((S1 :initform 5.4 :type number) 
                 (S2 :allocation :class))

(defclass C2 (C1) ((S1 :initform 5 :type integer)
                   (S2 :allocation :instance)
                   (S3 :accessor C2-S3))
  (:reader-prefix C2-))

(defclass C3 (C2) ((S2 :allocation :none))) 

\endscreen!

C1 has an {\bf :instance} slot named S1, whose default initial value is 5.4, 
and whose value is constrained to be a number.   C1 also has a {\bf :class} 
slot named S2.

C2 has access to an {\bf :instance} slot named S1, whose default initial value 
is 5, and whose value is constrained to satisfy 
{\bf (typep value '(and integer number))}.  (Since {\bf integer} is a subtype of
{\bf number}, this simplifies to {\bf (typep value 'integer)}.)
C2 has access to two {\bf :instance} slots, named S1 and
S2.  C2 has methods defined for reading the value  
of its slots; these methods are for the generic functions named:  C2-S1,
C2-S2, and C2-S3.  There is also a {\bf setf} method for use with C2-S3.

C3 has access to an {\bf :instance} slot named S1, whose default initial value
is 5, and whose value is constrained to satisfy 
{\bf (typep value '(and integer number))}.
C3 also has access to a slot named S3.  C3 has  
methods applicable for reading the value of the slots S1, S2, and S3.  
Note that although C3 has a method for reading the value of slot S2, it 
does not have access to that slot, so using the method would signal 
an error.  

\endsubSection%{Examples of Inheritance}

\beginsubSection{Redefining Classes}  

When a {\bf defclass} form is evaluated and a class with the given name
already exists, the existing class is redefined.   
Redefining a class modifies the existing class object to reflect 
the new class definition; it does not create a new class object for the
class.  Methods applicable to the class remain, except for any methods
created by the {\bf :accessor}, {\bf :reader}, {\bf :accessor-prefix},
or {\bf :reader-prefix} options, when those options have been changed in
the new {\bf defclass} form.

The \CLOS\ guarantees that {\bf defclass} can be used to change the
definition of an existing class that was previously defined by {\bf
defclass}, as long as the {\bf :metaclass} option is not used in either
the old or the new definition.  Whether {\bf defclass} is allowed to
change the metaclass is up to the implementor of the particular
metaclass.  ``The \CLOS\ Meta-Object Protocol,'' will describe how to
control this.
 
When a class is redefined, the changes are propagated to instances of 
that class, and instances of any of its subclasses.   This updating 
occurs upon the next access of an instance whose class (or any 
superclass) has been redefined.  In this context, an instance is 
accessed when a generic function is called with the instance as an
argument that is used for method selection, or when {\bf slot-value}
is called with the instance as an argument.  Updating an instance does 
not change its identity as defined by the {\bf eq} function.  The 
updating process changes the slots of that particular  
instance, but it does not create a new instance.  Whether updating an
instance consumes storage is implementation-dependent.  

Updating an instance calls {\bf change-class}, which is described in the
Programmer Interface chapter.   Note that when redefining a class, it is
possible to delete slots and add new slots.   When an instance is
updated, any new slots are initialized, and the values of any deleted
slots are discarded.  {\bf change-class} preserves the values of slots
that are common between the old and new versions of the class. 

Specifically, for each {\bf :allocation} {\bf :instance} slot of the new 
version of the class, if there is a slot by the same name in the 
old version of the class (with any 
{\bf :allocation} other than {\bf :none}), the slot's value is  
preserved.  This means that if the slot has a value, the value returned 
by {\bf slot-value} after the {\bf change-class} is {\bf eql} to the 
value returned by {\bf slot-value} before the {\bf change-class}. 
Similarly, if the slot is uninitialized, it remains 
uninitialized, and no error is signalled. 

Each {\bf :allocation} {\bf :instance} slot of the new version of the 
class with no 
slot by the same name in the old version of the 
class is initialized to the value of 
the {\bf :initform} of the new class, or remains uninitialized if the 
new version of the class has no {\bf :initform}.  This is the same as the 
initialization done by {\bf make-instance}, except that no 
initialization methods are invoked and no {\bf make-instance} 
initialization arguments are present. 

When a class is redefined in such a way that changes the set of slots in
an instance, or their order in storage, the generic function {\bf
class-changed} is run on instances as part of the updating process.  A
{\it obsolete\/} class object is created for this purpose.  This class
has no name.  The only instances of this class that can ever exist are
those created as the {\it previous\/} argument to a {\bf class-changed}
method.  All methods applicable to the class before redefinition,
including methods created by the {\bf :accessor}, {\bf :reader}, {\bf
:accessor-prefix}, and {\bf :reader-prefix} options, become applicable
to the obsolete class also.  This allows a {\bf class-changed} method to
extract information from its {\it previous\/} argument.  Thus
programmers can define their own methods for {\bf class-changed} to
initialize new slots differently from {\bf make-instance}, or copy
information from a slot in the old version of the instance to a
differently-named slot in the new version of the instance.  See the
description of the {\bf change-class} and {\bf class-changed} functions.

\endsubSection%{Redefining Classes}

\endSection%{Inheritance}

\beginSection{Integrating Types and Classes}

The \CLOS\ maps the Common Lisp type space into the space of classes.
Many but not all of the predefined Common Lisp type specifiers have a
class associated with them, with the same name as the type.  
For example, an array is of type {\bf 
array}, and of class {\bf array}.  Every class has a corresponding 
type with the same name as the class. 

A class that corresponds to a predefined Common Lisp type is
called a {\bit standard type class\/}.  Each standard type class has the
class {\bf standard-type-class} as a metaclass.   Users can write methods that
discriminate on any primitive Common Lisp type that has a corresponding class.
However, it is not allowed to make an instance of a standard type class 
with {\bf make-instance} or to include a standard type class as a 
superclass of a class.  Figure~1-1 lists the standard type classes.
Figure~1-2 displays part of the lattice of standard type classes.

[Figure 1-1, standard type classes, should go here.
Caption:  Standard type classes.  These classes correspond to predefined
Common Lisp types.  The class nil has no instances.]

Creating a type by means of {\bf defstruct} creates a class in this
lattice.  Such a class is an instance of {\bf structure-class} and a
direct subclass of the class that corresponds to the type given as
its {\bf :includes} argument, if any. 

%If no classes are included, the new class
%is a direct subclass of the class {\bf t}.

%Removed because the Figure 1-2 should show the ordering.   -Sonya
%Will you fix it to reflect only those types that have classes?   
%Converting a partial ordering to a total ordering for the sake of brevity,
%classes are ranked here in order from most specific to least specific:
%
%{\bf rational} {\bf float} {\bf number} {\bf symbol} {\bf list} {\bf
%vector} {\bf array} {\bf sequence}  

%Removed because we aren't having classes for all these types.  -Sonya 
%The following precedence relations hold among classes:
%{\bf list} has precedence over {\bf symbol} (for {\bf nil});
%{\bf array} has precedence over {\bf sequence} (for vectors);
%{\bf vector} has precedence over {\bf simple-array} (for simple-vectors);
%{\bf bit-vector} has precedence over {\bf simple-array} (for simple-bit-vectors);
%and {\bf string} has precedence over {\bf simple-array} (for simple-strings).
 
%Removed because the idea of abstract classes is gone.   -Sonya 
%The classes {\bf number}, {\bf integer}, {\bf rational}, {\bf float},
%{\bf list}, and {\bf sequence} are {\bit abstract classes}, that is,
%they can never be directly instantiated.  The function {\bf class-of}
%will never return one of these classes.

\eject

%Note:  it's easier to keep the lattice figure out of this file,
%and in a different file.   For one thing, it makes it easy to
%comment it out when we want to print it here.   
%
%\input lattice 

\endSection%{Integrating Types and Classes}


\beginSection{Determining the Class Precedence List}

\beginsubSection{Computing the Class Precedence List}

The class lattice imposes a partial ordering on the classes in the
lattice, called the {\bit lattice order\/}.  This partial ordering is
generated by
a set of ordered pairs of classes called $R\sub l$
where $$R\sub l=\{(C\sub
1,C\sub 2)\,|\,\hbox{$C\sub 2$ is a direct superclass of $C\sub 1$}\}$$
The lattice order is the transitive closure of $R\sub l$.

The {\bf defclass} form for a class provides a total ordering on the
direct superclasses for that class, called the {\bit local precedence order\/};
the local precedence order is an ordered list of the direct superclasses
of a class.  We form a second partial ordering from the set of local
precedence orders in the class lattice.  This second partial ordering
is generated by a set of ordered pairs of classes called
$R\sub p$.  For every class $C$, if the local precedence order for that
class is $(C\sub 1\ldots C\sub n)$, then $(C\sub i,C\sub {i+1})\in
R\sub p$ for $1\leq i<n$.

We define a set called $R=R\sub l\cup R\sub p$.
$R$ may or may not generate a partial ordering depending
on whether $R\sub l$ and $R\sub p$ are
consistent; we assume they are consistent and that $R$ is a partial
ordering. When $(C\sub 1,C\sub 2)\in R$ we say that $C\sub 1$ {\bit
precedes} $C\sub 2$.

Let $S\sub C$ be the set of $C$ and its superclasses; let $R'$ be
the subset of $R$ where $$R'=\{(C,D)\,|\,\hbox{$C\in$ $S\sub
C$ and $D\in$ $S\sub C$}\}$$ 

That is, $R'$ contains the pairs
that involve the classes in $S\sub C$.  To compute the class
precedence list at $C$, we topologically sort the elements of 
$S\sub C$ with
respect to the partial ordering $R'$.   When the topological sort
must select a class from a set of two or more classes, none
of which are preceded by other classes with respect to $R'$, the class
selected is chosen deterministically, as described below.

We require that an implementation of \CLOS\ signal an error if the
partial ordering is inconsistent.

\beginsubsubsection{Topological Sorting}

Topological sorting proceeds by finding a class $C$ in~$S\sub C$
such that no other class precedes that element according to the
elements in~$R'$.  $C$ is placed first in the result.  We remove $C$ from
$S\sub C$, and we remove all relations of the form $(C,D)$,
$D\in S\sub C$, from $R'$. We repeat the process, adding
classes with no predecessors at the end of the result.  We stop when
no element can be found that has no predecessor.

If $S\sub C$ is not empty and the process has stopped, the
order $R$ is inconsistent: if every class in the finite set of classes
is preceded by another, then the relation contains a loop, and there
are two classes, $C\sub 1$ and $C\sub 2$, such that $C\sub 1$ precedes
$C\sub 2$ and $C\sub 2$ precedes $C\sub 1$.

Sometimes there are several classes from $S\sub C$ with no predecessors.
In this case we select the one that has a direct subclass rightmost
in the class precedence list computed so far.  If that subclass has more
than one direct superclass among the candidates, take the superclass
that is most specific according to the subclass's local precedence
order.  This algorithm does a good job of keeping related classes together.

In detail:
Let $\{N\sub 1\ldots N\sub m\}$, $m\geq 2$, be the classes from
$S\sub C$ with no predecessors.  Let $\{C\sub 1\ldots C\sub n\}$,
$n\geq 1$, be the class precedence list constructed so far.
$C\sub 1$ is the most specific class, whose class precedence list is
being computed.  $C\sub n$ is the least specific class accepted so far.
For $i$ from $n$ down to $1$, let $\{Q\sub 1\ldots Q\sub k\}$, $k\geq 1$, be 
the direct superclasses of $C\sub i$.  For $j$ from $1$ up to $k$, if
$Q\sub j\in\{N\sub 1\ldots N\sub m\}$, set $C\sub {n+1}$ to $Q\sub j$
and proceed with the topological sort.

\endsubsubsection%{Topological Sorting}

\beginsubsubsection{Examples}

Here is an example of determining a class precedence list.  The classes
are defined:

\screen!

(defclass pie (apple cinnamon) ())

(defclass apple (fruit) ())

(defclass cinnamon (spice) ())

(defclass fruit (food) ())

(defclass spice (food) ())

(defclass food () ())
\endscreen!

The set $S$~$=$ $\{${\tt pie apple cinnamon fruit spice food}$\}$. The
set $R'$~$=$ $\{${\tt (pie, apple) (pie, cinnamon)
(apple, cinnamon) (apple, fruit) (cinnamon, spice)
(fruit, food) (spice, food)}$\}$.

The class {\tt pie} is not preceded by anything, so it comes first;
the result so far is {\tt (pie)}.  We remove {\tt pie} from $S$ and
relations mentioning {\tt pie} from $R'$ and get $S$~$=$ $\{${\tt
apple cinnamon fruit spice food}$\}$ and $R'$~$=$ $\{${\tt
(apple, cinnamon) (apple, fruit) (cinnamon, spice)
(fruit, food) (spice, food)}$\}$.

The class {\tt apple} is not preceded by anything, so it is next; the
result is {\tt (pie apple)}. Removing {\tt apple} and the relevant
relations we get $S$~$=$ $\{${\tt cinnamon fruit spice food}$\}$ and
$R'$~$=$ $\{${\tt (cinnamon, spice) (fruit, food)
(spice, food)}$\}$.

The classes {\tt cinnamon} and {\tt fruit} are not preceded by
anything, so we look at which of these two has a direct subclass
rightmost in the class precedence list computed so far.
{\tt apple} is a direct subclass of {\tt fruit} and is rightmost
in the precedence list.  Therefore we select {\tt fruit} next, and the result so far
is {\tt (pie apple fruit)}.  $S$~$=$ $\{${\tt cinnamon spice
food}$\}$; $R'$~$=$ $\{${\tt (cinnamon, spice) (spice, food)}$\}$.

The class {\tt cinnamon} is next, giving the result so far as {\tt (pie apple
fruit cinnamon)}.  $S$~$=$ $\{${\tt spice food}$\}$; $R'$~$=$
$\{${\tt (spice, food)}$\}$.

The classes {\tt spice} and {\tt food} are added in that order, and the class
precedence list is {\tt (pie apple fruit cinnamon spice food)}.

It is possible to write a set of class definitions that cannot be 
ordered.   For example: 

\screen!

(defclass new-class (fruit apple) ())

(defclass apple (fruit) ())
\endscreen!

The class {\tt fruit} must precede {\tt apple} because the local
ordering of superclasses is preserved.  The class {\tt apple} must
precede {\tt fruit} because a class always precedes its own
superclasses.  When this situation occurs, an error is signalled when
the system tries to compute the class precedence list.

Note the following example, which appears at first glance to be a
conflicting set of definitions: 

\screen!

(defclass pie (apple cinnamon) ())

(defclass pastry (cinnamon apple) ())
\endscreen!

The ordering for {\tt pie} is:  {\tt (pie apple cinnamon)}  

The ordering for {\tt pastry} is:  {\tt (pastry cinnamon apple)}

There is no problem with the fact that {\tt apple} precedes {\tt
cinnamon} in the ordering of the superclasses of {\tt pie}, but not in the
ordering for {\tt pastry}.  However, it is not possible to build a new class
that has both {\tt pie} and {\tt pastry} as superclasses.

\endsubsubsection%{Examples}

\endsubSection%{Computing the Class Precedence List}

\endSection%{Determining the Class Precedence List}


\beginSection{Generic Functions and Methods}

\beginsubSection{Introduction to Generic Functions}

A generic function object comprises a set of {\bit methods\/}, a
lambda-list, a method-combination type, and possibly some options.

Like an ordinary Lisp function, a generic function takes arguments,
performs an operation, and perhaps returns useful values.  An ordinary
function has a single body of code that is always executed when the
function is called.  A generic function might perform a different
series of operations and combine the results of the operations in
different ways, depending on the class or identity of one or more of its
arguments.  An argument that determines which method or methods are to
be run is called a {\bit specialized argument\/}.  A generic function
can have several methods associated with it, and the class or identity of each
specialized argument to the generic function indicates which method or
methods to use.

Ordinary functions and generic functions are called with identical
syntax:

{\tt ({\it function-name arguments} $\ldots$ )}
 
Generic functions are true functions that can be passed as arguments and
used as the first argument to {\bf funcall} and {\bf apply}.

Ordinary functions have a definition that is in one place; generic 
functions have a distributed definition.  The definition of a generic
function can be found in a set of {\bf defmethod} forms, possibly along
with a {\bf defgeneric-options} form that provides information about the
contract of the generic function.  Evaluating these forms produces a
generic function object.  

Generic functions are named in the same way 
that ordinary functions are named; that is, the generic function 
object can be stored as the function definition of a symbol. 
This is the only association from the name to the generic function.  
Both {\bf defmethod} and {\bf defgeneric-options} use {\bf symbol-function}  
to find the generic function they affect.   
When a generic function is associated with a symbol, that name 
is in a certain package and can be exported if it is part of an external 
interface.  

When a new {\bf defgeneric-options} form is evaluated and a generic
function of the given name already exists, the existing generic function
object is modified.  This does not modify any of the methods associated
with the generic function.  When a {\bf defgeneric-options} form is
evaluated and no generic function of this name exists, a generic
function is created with no methods.

When a {\bf defmethod} form is evaluated 
and a generic function of the given name already exists, the existing 
generic function object is modified to contain the new method. 
When a {\bf defmethod} form is evaluated and no generic
function with that name exists, a generic function is created with
default values for the argument precedence order, the generic function
class, the method class, and the method-combination type.  The lambda
list of the generic function is congruent with the argument list of the
method being defined.  

\endsubSection%{Introduction to Generic Functions}

\beginsubSection{Introduction to setf Generic Functions}

A setf generic function is called in an expression such as 
{\tt (setf ({\it function-name arguments}) {\it new-value})}.

One example of a setf generic function is the automatically generated  
setf function created when the {\bf :accessor} option is given to
{\bf defclass}.   The {\bf :accessor} option defines a reader generic
function by a given name.   It also defines a generic function that
is invoked when {\bf setf} is used with the reader function.   If the
reader function is named {\it ship-color\/}, the corresponding 
setf function is invoked via the expression:  
{\tt (setf (ship-color {\it ship\/}){\it new-value\/})}.  

The macro {\bf defgeneric-options-setf} can be used to define a setf
generic function.  
The macro {\bf defmethod-setf} can be used to define a method for a setf 
generic function.  

Note that unlike other generic functions, setf generic functions do not have names. 
{\bf defmethod-setf} and {\bf defgeneric-options-setf} use  
{\bf get-setf-generic-function} to find the generic function they affect.   
 
\endsubSection%{Introduction to setf Generic Functions}

\beginsubSection{Introduction to Methods}

A method object contains a method function, a set of {\bit parameter
specializers\/} that specify when the given method is applicable, and 
a set of {\bit qualifiers\/} that are used by the method combination to 
distinguish among methods.  

The macro {\bf defmethod} is used to create a method object.  A {\bf
defmethod} form contains the code that is to be run when the
specialized arguments to the generic function cause the method that it
defines to be selected.  If a {\bf defmethod} form is evaluated and a
method object corresponding to the given generic function name, 
parameter specializers, and qualifiers already exists, the 
new definition replaces the old. 

Each method has a ``specialized'' lambda list, which indicates which of
its arguments are to be used for method selection.  
Only required parameters can be specialized.   A future extension might 
allow optional and keyword parameters to be specialized.
Methods can have arguments not intended to be used for selection;
such parameter specifiers are as in {\bf defun} syntax.  
A parameter specifier indicating an argument to be used for method selection
is a list, {\tt ({\it variable-name parameter-specializer\/})}, 
where {\it parameter-specializer\/} is one of:

\beginlist

\item{\bull} The name of any class.

\item{\bull} ({\bf quote} {\it object\/})

%\item{\bull} A symbol naming a standard type class.  These classes are listed
%in Figure~1-1.
%corresponding to one of these Common Lisp types:

%\Vskip 1pc!
%\boxfig
%{\bf\tabskip 0pt plus 1fil
%\halign to \hsize{&#\hfil\cr
%array&integer&rational\cr
%bit-vector&list&readtable\cr
%character&long-float&sequence\cr
%compiled-function&null&short-float\cr
%complex&number&single-float\cr
%cons&package&string\cr
%double-float&pathname&symbol\cr
%float&random-state&t\cr
%hashtable&ratio&vector\cr
%}}
%\caption{ \break--use of break gets another line--lgd}
%\endfig

\endlist

Parameter specializers are a subset of type-specifiers, including only
those type-specifiers with a corresponding class, and {\bf quote}. 
{\bf typep} can be used to determine whether a method is applicable for a 
given argument.  Therefore, this standard  
includes an upward-compatible extension of the Common Lisp type system,
and does not create another type system.  
Note that in general a parameter specializer cannot be a type specifier list,
such as {\tt ({\bf vector single-float})}.   The only parameter specializer that
can be a list is {\tt ({\bf quote} {\it object\/})}.

A method can have a specialized parameter of 
{\tt ({\bf quote} {\it object\/})};  this method is selected if 
{\tt ({\bf eql} {\it argument 'object\/})} 
is true for the corresponding argument to the generic function. 
This proposal requires that Common Lisp be modified to include 
{\tt ({\bf deftype quote} ({\it object\/}) `({\bf member} {\it ,object\/}))}.

A method with no specialized parameters is 
a {\bit default method\/}; it is always part of the generic
function, but often shadowed by a more specific method.   A default
method can also have a parameter specializer of {\bf T}; this is the
same as if that parameter had no specializer, since {\bf T} is the 
class of all objects.  

%I agree with dropping these terms, since we don't use them anywhere.  -Sonya
%Sometimes methods with one specialized parameter are distinguished from
%methods with more than one specialized parameter.  
%Usually, when this is done, a method
%that has only one specialized parameter is called a {\bit classical\/}
%method; a method with more than one specialized parameter is called a
%{\bit multi-method\/}.

Methods can have {\bit qualifiers}, which give the method combination
procedure a way to distinguish between methods.  A method that has one
or more qualifiers is called a {\bit qualified\/} method.
A method with no qualifiers is an {\bit unqualified method}. 
A qualifier is any object other than a list; in other words, 
any non-{\bf nil} atom.  By convention, qualifiers are usually keyword
symbols.

\endsubSection%{Introduction to Methods}

\beginsubSection{Congruent Lambda-lists for all Methods of a Generic Function}

The {\it lambda-list\/} argument of {\bf defgeneric-options} specifies
the ``shape'' of lambda lists for the methods of that 
generic function.  All methods for the given generic function must be
congruent with this shape; this implies that the system can determine
whether a call is syntactically correct.  The shape of a lambda list
is defined by the number of required arguments, the number of optional
arguments, whether or not {\bf \&allow-other-keys} appears, the number and
names of keyword arguments, and whether or not {\bf \&rest} is used.

The rules are for congruence are:

[The following is a first approximation of these rules, which need
to be discussed further:]

\numitem{1.}Each method must have the same number of required arguments. 

\numitem{2.}Each method must have the same number of {\bf \&optional}
arguments, but methods can supply different defaults for {\bf
\&optional} arguments.

\numitem{3.}If {\bf \&allow-other-keys} is used by one method, all
methods must use it.

\numitem{4.}If {\bf \&allow-other-keys} is not used, each method must
allow the same number of {\bf \&key} arguments, and these keyword
arguments must have the same keywords across methods.

\numitem{5.}If {\bf \&rest} is used by one method, all methods must use it. 

\numitem{6.}The use of {\bf \&aux} need not be consistent across methods.  

The method receives the same arguments that the generic function 
received. 

Note that if a method is defined and the generic function does not already
exist, a generic function is created with a lambda list that is congruent
with the argument list of the method being defined. 

\endsubSection%{Congruent Lambda-lists for all Methods of a Generic Function}

\endSection%{Generic Functions and Methods}

\beginSection{Method Selection and Combination}

When a generic function is called with particular arguments, it must decide
what code to execute.  We call this code the {\bit effective method\/} for
those arguments.  The effective method can be one of the methods for the
generic function or a combination of several of them.

Choosing the effective method involves the following decisions: 

\beginlist

\item{\bull} Which method (or methods) to call

\item{\bull} The order in which to call the methods

\item{\bull} Which value (or values) to return 

\item{\bull} Which method to call next when {\bf call-next-method} is used

\endlist

The effective method is determined by the following four-step procedure:

\numitem{1.}{\it Select the set of applicable methods.\/}

Given a generic function and a set of arguments, the applicable methods are
all methods for that generic function whose parameters are satisfied by
their corresponding arguments.  An argument satisfies a parameter if 
one of the following conditions is true:

\beginlist

\item{\bull} The parameter is not specialized.

\item{\bull} The parameter is specialized with a class name {\it C\/} and
{\tt ({\bf typep} {\it argument 'C\/})} is true.  In other words, the 
class of the argument is the class named in the specializer or is a
subclass of it.

\item{\bull} The specializer is {\tt ({\bf quote} {\it object\/})}
and {\tt ({\bf eql} {\it argument 'object\/})} is true for the 
corresponding argument to the generic function. 

\endlist

\numitem{2.}{\it Sort the applicable methods by precedence order,
putting the most specific method first.\/}

To compare the precedence of two methods, examine their parameters in
order.  The default examination order is from left to right, but an 
alternative order may be specified by the {\bf :argument-precedence-order}
option to {\bf defgeneric-options}.

Compare the specializers of corresponding parameters from each method.  
An unspecialized parameter has a specializer of {\bf t}. 
The first pair of parameter specializers that are not equal determine the 
precedence.  When a pair of parameter specializers are equal,  
proceed to the next pair and compare them for equality.  

If both parameter specializers are class names, consider the class 
precedence list of the argument.  The more specific of the two methods
is the method whose parameter specializer appears earlier in the class 
precedence list.  Due to the way the set of applicable methods is 
chosen, the parameter specializers are guaranteed to be present in the
class precedence list of the class of the argument.
{\bf t} is implied at the end of each class precedence list, so it 
is less specific than any other class.

%This seems more confusing than helpful: --Moon 
%Note that the ordering is simply alphabetical
%with respect to the argument precedence order and the class precedence list.

If one parameter specializer is {\tt ({\bf quote} {\it object\/})}, it is more
specific than any class.  If both parameter specializers are quoted
objects, the specializers are equal (otherwise the two methods would
not both have been applicable for this argument).

The resulting list of applicable methods has the most specific
method first and the least specific method at the end.    

Note that two methods with identical specializers but different
qualifiers are not ordered by this algorithm.  Normally the two methods
play different roles in the effective method because they have different
qualifiers, and no matter which order they appear in, in the result of
step 2, the effective method is the same.

\numitem{3.}{\it Apply method combination to the sorted list of applicable methods,
producing the effective method.\/}

Considering the simplest case first, if standard method combination is used
and all applicable methods are primary, the effective method is the 
most specific method.  That method can call the next most specific method
using the macro {\bf call-next-method}.

In general, the effective method is some combination of the applicable
methods.  It is defined by a Lisp form that contains calls to some or all
of the applicable methods, returns the value or values to be returned by
the generic function, and optionally makes some of the methods reachable
via {\bf call-next-method}, rather than calling them directly.  This Lisp
form is the body of the effective method; the object system augments it
with an appropriate lambda-list to make it a function.

Method qualifiers determine the role of each method in the effective
method.  The meaning of the qualifiers of a method is defined entirely by
this step of the procedure.  If an applicable method has an unrecognized
qualifier, this step reports an error and does not include that method in
the effective method.

When standard method combination is used together with qualified methods, 
the effective method is produced as described in the section
``Standard Method Combination''.

The programmer can select another type of method combination by using the
{\bf :method-combination} option of {\bf defgeneric-options}.  This allows
the programmer to customize this step of this procedure without needing to 
consider what happens in the other steps.   (The other steps of this 
procedure can be customized using meta-objects.)

New types of method combination can be defined using the 
{\bf define-method-combination} macro, which is provided in 
the basic Programmer Interface.  The body of the 
{\bf define-method-combination} returns the Lisp form that defines the
effective method.  See the section ``Declarative Method Combination''.

The meta-object level also offers a mechanism for defining new types of
method combination.  The generic function {\bf compute-effective-method}
receives as arguments the generic function, the sorted list of applicable
methods, the name of the method combination type, and the list of options
specified in the {\bf :method-combination} option of
{\bf defgeneric-options}, and returns the Lisp form that defines the
effective method.  The programmer can define a method for
{\bf compute-effective-method} directly, using
{\bf defmacro}, or indirectly, using {\bf define-method-combination}.

\numitem{4.}{\it Apply the effective method to the generic function arguments.\/}

The effective method is called with the same arguments that were passed
to the generic function.  Whatever values it returns are returned as
the values of the generic function.

In the simplest implementation, the generic function would compute the
effective method each time it was called.  In practice, this is too
inefficient for most implementations.  Instead they employ a variety of
optimizations of the four-step procedure, such as precomputation into
tables, compilation, and/or caching to speed things up.  Some illustrative
examples (not exhaustive) are:

\beginlist

\item{\bull} Use a hash table keyed by the class of the arguments to
store the effective method.

\item{\bull} Compile the effective method and save the resulting
compiled-function in a table.

\item{\bull} Recognize the Lisp form as an instance of a pattern of
control structure and substitute a closure of a function that implements
that structure.

\item{\bull} Examine the parameter specializers of all methods for the
generic function and enumerate all possible effective methods.  Combine
these effective methods, together with code to select from among them by
testing the arguments, into a single function and compile it.
Call that function whenever the generic function is called.

\endlist

The Lisp form computed by step~3 as the body of the effective method serves
as a more general interface.  For example, a tool that determines which
methods are called and presents them to the user works by going through the
first three steps of the above procedure and then analyzing the form to
determine which methods it calls, instead of evaluating it.

Separating the procedure of determining the effective method from the
procedure of invoking methods and combining their results, and using a Lisp
form as the interface between these procedures, allows for more optimizations
to the speed of the code and also enables more powerful programming tools
to be written.

\endSection%{Method Selection and Combination}

\beginSection{Standard Method Combination}

Standard method combination is used by default if the programmer does
not specify another type of method combination.   Standard method combination 
recognizes four roles for methods, according to method qualifiers.   
Primary methods define the main action of the effective method,  
while auxiliary methods modify that action in one of three ways.
The four valid method qualifiers for standard method combination are:  
no qualifier at all, {\bf :before}, {\bf :after}, {\bf :around}.  
The corresponding method roles are: 

\def\numhangsize{60pt}

\numitem{Primary methods:}These are unqualified methods.  The most specific 
primary method is called.  Inside the body of a primary method, the macro 
{\bf call-next-method} may be used to pass control to the next most specific 
primary method.  When that method returns, the first primary method can
execute more code, perhaps based on the returned value or values. 
If {\bf call-next-method} is not used, only the most specific 
primary method is called.   

\numitem{{\bf :before} methods:}These methods have the keyword 
{\bf :before} as their only qualifier.  They specify code that runs before
the primary method.  The most specific {\bf :before} method is called first.

\numitem{{\bf :after} methods:}These methods have the keyword {\bf :after}
as their only qualifier.  They specify code that runs after the primary
method.  The least specific {\bf :after} method is called first.

\numitem{{\bf :around} methods:}These methods have the keyword {\bf :around} as
their only qualifier.  The most specific {\bf :around} method is called. 
Inside the body of an {\bf :around} method, the macro {\bf call-next-method} can be
used to immediately call the ``next method'' (see below).  When the next
method returns, the {\bf :around} method can execute more code, perhaps
based on the returned value or values.  By convention, {\bf :around} methods
almost always use {\bf call-next-method}.

\def\numhangsize{25pt}

The semantics of standard method combination are:

\beginlist

\item{\bull} If there are any {\bf :around} methods, the most specific
{\bf :around} method is called, and supplies the value or values of the
generic function.

\item{\bull} If an {\bf :around} method uses {\bf call-next-method}, the
next most specific {\bf :around} method is called, if one is applicable.

\item{\bull} If there are no {\bf :around} methods at all, or if {\bf
call-next-method} is called by the least specific {\bf :around} method, the
other methods are called in the following way:

\beginlist

\itemitem{--} All the {\bf :before} methods are called, in
most specific first order; values are ignored.

\itemitem{--} The most specific primary method is called, and supplies
the value or values returned by the generic function (or by {\bf
call-next-method} in the least specific {\bf :around} method).  If it calls
{\bf call-next-method}, the second most specific primary method is
called, and so on until there are no more primary methods.  An error is
signalled if {\bf call-next-method} is used and there is no applicable
primary method to call.

\itemitem{--} All the {\bf :after} methods are called in
most specific last order; values are ignored.

\endlist

\endlist

\beginRemarks

In standard method combination, if there are any applicable methods at all,
then there must be an applicable primary method to produce the value or
values.  In cases where there are applicable methods but no primary method
an error is signalled.

An error is signalled if {\bf call-next-method} is used and there is no
next method remaining.

An error is signalled if {\bf call-next-method} is used in a {\bf :before}
or {\bf :after} method.

Standard method combination allows no more than one qualifier per method.

Running {\bf :before} methods in most specific first order while running
{\bf :after} methods in least-specific-first order provides a degree of
transparency.  If class X modifies the behavior of its superclass Y by
adding an auxiliary method, the partitioning of Y's behavior into
primary, {\bf :before}, and {\bf :after} methods is transparent.
Whether class Y defines these methods directly or inherits them from
its superclasses is transparent.
Class X's {\bf :before} method runs before {\it all\/} of class Y's
methods.  Class X's {\bf :after} method runs after {\it all\/} of class Y's
methods.

{\bf :around} methods are an exception to this rule; they do not combine
transparently.  All {\bf :around} methods run before any primary methods
run.  Thus a less specific {\bf :around} method runs before a more specific
primary method.

If only primary methods are used, standard method combination behaves like
CommonLoops.  If {\bf call-next-method} is not used, only the most specific
method is invoked.  That is, more general methods are shadowed by more
specific ones.  If {\bf call-next-method} is used, the effect is the same
as {\bf run-super} in CommonLoops.

If {\bf call-next-method} is not used, standard method combination behaves
like {\bf :daemon} method combination of New Flavors, with {\bf :around}
methods playing the role of whoppers, except that the ability to reverse
the order of the primary methods has been removed.

\endRemarks

\endSection%{Standard Method Combination}


\beginSection{Declarative Method Combination}

The programmer can define new forms of method combination using
the {\bf define-method-combination} macro.  This allows customization
of step~3 of the method combination procedure.  There are two forms
of {\bf define-method-combination}.  The short form is a very
easy to use facility for the cases that have been found to be
most commonly needed.

The long form is more powerful but more verbose.  It resembles
{\bf defmacro} in that the body is an expression that computes
a Lisp form, usually using backquote.  Thus arbitrary control 
structures can be implemented.  The long form also allows arbitrary
processing of method qualifiers.

To specify that a generic function should use a newly-defined type of
method combination, use the {\bf (:method-combination {\it name\/})}
option to {\bf defgeneric-options} or {\bf defgeneric-options-setf}.

\beginsubSection{Long Form of Define-method-combination}

\screen!

[The following syntax expression needs to be converted to TEX:]

(DEFINE-METHOD-COMBINATION name lambda-list                     [macro]
      ( {(variable { {qualifier-pattern}+ | predicate}
                   {keyword argument}*)}* )
  {declaration | doc-string}*
  {form}*)

\endscreen!

{\it Name\/} is a symbol, usable as a
name for this in the {\bf :method-combination} option to {\bf
defgeneric-options} or {\bf defgeneric-options-setf}.  By convention,
non-keyword, non-{\bf nil} symbols are usually used.

{\it lambda-list\/} is an ordinary lambda-list.  It receives any arguments provided
after {\it name\/} in the {\bf :method-combination} option to 
{\bf defgeneric-options} or {\bf defgeneric-options-setf}.

A list of method-group specifiers follows.  Each specifier selects a subset
of the applicable methods to play a particular role, either by matching
their qualifiers against some patterns or by testing their qualifiers with 
a predicate.  These method-group specifiers define all method qualifiers
that can be used with this type of method combination.  If an applicable 
method does not fall into any method-group, the system reports the error
that the method is invalid for the kind of method-combination being
used.

Each method-group specifier names a variable.  During the execution of the
body forms, the variable is bound to a list of the methods in the
method-group, in most specific first order.

A qualifier-pattern is a list or the symbol {\bf *}.  A method matches a 
qualifier-pattern if the method's list of qualifiers is {\bf equal} to the
qualifier-pattern, except that the symbol {\bf *} in a qualifier-pattern
matches anything.  Thus a qualifier-pattern can be the empty list {\bf ()} 
(which matches unqualified methods), the symbol {\bf *} (which matches all 
methods), a true list (which matches methods with the same number of
qualifiers as the length of the list, when each qualifier matches the
corresponding list element), or a dotted list that ends in the symbol
{\bf *} (the {\bf *} matches any number of additional qualifiers).
(True lists are non-dotted lists, as defined in {\it Common Lisp: The
Language\/}.) 

Each applicable method is tested against the qualifier-patterns and
predicates in left-to-right order.  As soon as a qualifier-pattern matches
or a predicate returns true, the method becomes a member of the
corresponding method-group and no further tests are made.  Thus if a method
could be a member of more than one method-group, it joins only the first
such group.  If a method-group has more than one qualifier-pattern, a
method need only satisfy one of the qualifier-patterns to be a member of
the group.

The name of a predicate function can appear in place of the
qualifier-patterns in a method-group specifier.  The predicate is called
for each method that has not been assigned to an earlier method-group, with
one argument, the method's qualifier list.  The predicate should return
true if the method should be a member of the method-group.  A predicate is
distinguishable from a qualifier-pattern because it is a symbol other than
{\bf nil} or {\bf *}.

Method-group specifiers can have keyword options after the
qualifier-patterns or predicate.  Keyword options are distinguishable from
additional qualifier patterns because they are not lists nor the symbol
{\bf *}.  The keyword options are:

\def\numhangsize{60pt}

\numitem{{\bf :description} {\it format-string\/}} \break
Provides a description of the role of methods in this method-group.
Programming environment tools use
% TEX won't let me use #' in the next line
{\bf (apply (function format) stream {\it format-string\/}
(method-qualifiers {\it method\/}))}
to print this description, which is expected to be concise, such 
as one or two words.  
This keyword option allows the description of a method qualifier to be
defined in the same module that defines the semantic meaning of the
method qualifier.
In most cases {\it format-string\/} will not contain any format directives,
but they are available for generality.
If {\bf :description} is not specified, a default description is generated
based on the variable name, the qualifier patterns, and whether this
method-group includes the primary methods.
The argument {\it format-string\/} is not evaluated.

\numitem{{\bf :order} {\it order\/}} \break
Specifies the order of methods.
The argument is a form evaluating to {\bf :most-specific-first} or
{\bf :most-specific-last}.  If it evaluates to any other value,
an error is signalled.  This keyword option is a convenience
and does not add any expressive power.  It is provided so that programmers
do not have to write the ugly {\bf case} expression seen in the examples
below, and especially to avoid tempting programmers to omit the error checking.
If {\bf :order} is not specified, it defaults to {\bf :most-specific-first}.

\numitem{{\bf :required} {\it boolean\/}} \break
State whether at least one method in this method-group is required.  
If {\it boolean\/} is true (not {\bf nil}), and the method-group is empty 
(that is, no applicable methods match the qualifier-patterns or satisfy the
predicate), an error is signalled.  This keyword option is a convenience
and does not add any expressive power.  It is provided so that programmers
are not tempted to omit error checking.
If {\bf :required} is not specified, it defaults to {\bf nil}.
The argument {\it boolean\/} is not evaluated.

\def\numhangsize{25pt}

The use of method-group specifiers provides a convenient syntax for the
cliched code that has to be written for every kind of method combination,
to select methods, divide them among the possible roles, and perform the
necessary error checking.  It is possible to perform further filtering of
methods in the body forms, using normal list-processing operations and the
functions {\bf method-qualifiers} and {\bf invalid-method-error}.  It is
permissible to {\bf setq} the variables named in the method-group
specifiers and to bind additional variables.  It is also possible to bypass
the method-group specifier mechanism and do everything in the body forms.
This is accomplished by writing a single method group with {\bf *} as its only
qualifier-pattern; the variable is then bound to a list of all of the
applicable methods, in most specific first order.

The body {\it forms\/} compute and return the Lisp form that specifies how
the methods are combined, that is, the effective method.
The body of {\bf define-method-combination} resembles the body of
{\bf defmacro} and uses backquote in a similar way.
The function {\bf make-method-call} is also used in constructing the
Lisp form; it hides the implementation-dependent details of how
methods are called.  Programmers always use {\bf make-method-call} to
translate from the lists of method objects produced by the method-group
specifiers to Lisp forms that invoke those methods.
 
Erroneous conditions detected by the body should be reported with
{\bf method-combination-error} or {\bf invalid-method-error}; these functions
add any necessary contextual information to the error message and will use
the condition signalling system when and if it is adopted into Common Lisp. 

The body {\it forms\/} are evaluated inside of the bindings created by the
lambda-list and method-group specifiers.  Declarations at the head of
the body are positioned directly inside of bindings created by the
lambda-list, and outside of the bindings of the method-group variables. 
Thus method-group variables cannot be declared.

Within the body {\it forms\/}, the lexical variable {\bf generic-function}
is bound to the generic-function object, in case it is needed.

If a doc-string is present, it documents the method-combination type.  

The functions {\bf make-method-call}, {\bf method-combination-error}, and
{\bf invalid-method-error} can be called from the body {\it forms\/}, or
from functions called by the body {\it forms\/}.  The action of these three
functions can depend on dynamic variables bound by the object system before
calling the method-combination function.  These variables might contain the
parameter list of the effective method or other implementation-dependent
information.

Note that two methods with identical specializers but different qualifiers are 
not ordered by algorithm described in step 2 of the method selection and combination
process.  Normally the two methods play different roles in the effective method
because they have different qualifiers, and no matter which order they
appear in, in the result of step 2, the effective method is the  
same.  If the two methods play the same role, so that their order 
matters, implementations are encouraged to signal an error (this would 
happen as part of qualifier-pattern matching in {\bf define-method-combination}).  

\endsubSection%{Long Form of Define-method-combination}

\beginsubSection{Short Form of Define-method-combination}

% (DEFINE-METHOD-COMBINATION name operator {keyword argument}*)

\Defmac {define-method-combination} {name \star{\curly{keyword argument}}}

{\it Name\/} is a symbol, usable as a
name for this in the {\bf :method-combination} option to {\bf
defgeneric-options} or {\bf defgeneric-options-setf}.  By convention,
non-keyword, non-{\bf nil} symbols are usually used.

The short form defines {\it name\/} as a type of method combination that
produces a Lisp form {\bf ({\it operator method-call method-call...\/})}.

{\it operator\/} is a symbol that can be the name of a function, macro,
or special form.  By convention, {\it name\/} and {\it operator\/} are
often the same symbol, but this is not required.  {\it operator\/}
defaults to {\it name\/} unless specified by keyword option.

The short form of {\bf define-method-combination} is 
recognized when the second subform is a non-{\bf nil} 
symbol or is not present.
The long form of {\bf define-method-combination} is recognized 
when the second subform is a list.  

Keyword options for the short form are: 

\beginlist

\item{\bull}
{\bf :documentation} {\it string\/} documents the method-combination type.

\item{\bull}
{\bf :identity-with-one-argument} {\it boolean\/} enables an optimization
when {\it boolean\/} is true (the default is false).
If there is exactly one applicable method, and it is a primary method,
that serves as the effective method and {\it operator\/} is not called.
This optimization avoids the need to create a new effective method
and avoids the overhead of a function call.
Use this option with operators that are identity operators when 
applied to one argument, such as {\bf progn}, {\bf and}, {\bf $+$}, 
and {\bf max}.  

\item{\bull}
{\bf :operator} {\it operator\/} specifies the name of the operator.
If not specified, the name of the operator and the name of the method
combination type are the same.

\endlist

None of the subforms is evaluated.

A method combination procedure defined this way recognizes two roles for
methods.  An unqualified method is a primary method.  A method with the
keyword symbol with the same name as {\it name\/} as its one qualifier is
also a primary method.  Attaching this qualifier to a primary method
documents that this method is intended for use with an unusual form
of method combination and can make programs easier to understand.

A method with {\bf :around} as its one qualifier is an auxiliary method
that behaves the same as a {\bf :around} method in standard method
combination.

{\bf call-next-method} can only be used in {\bf :around} methods, not in
primary methods.

A method combination procedure defined this way accepts an optional 
argument named order, defaulting to {\bf :most-specific-first}.  A value of
{\bf :most-specific-last} reverses the order of the primary methods, without
affecting the order of the auxiliary methods.  Use
the {\bf (:method-combination {\it name\/} :most-specific-last)}
option to {\bf defgeneric-options} or {\bf defgeneric-options-setf}
to specify this.

A large fraction of the types of method combination needed by 
most programmers can be implemented with this short form, which is 
provided for convenience.   The short form automatically includes 
error-checking and support for {\bf :around} methods, thus saving the
programmer from writing that code, and avoids the need for the programmer to
use the backquote and comma, and learn the more complex syntax of the long form.

For example: 

\screen!

(define-method-combination and :identity-with-one-argument t) 

(defmethod func :and ((x class1) y) ...)

\endscreen!

The equivalent of this example in the long form is:

\screen!

(define-method-combination and 
        (&optional (order ':most-specific-first))
        ((around (:around))
         (primary () (:and) :order order :required t))
  (make-method-call `(,@around
                      ,(make-method-call primary
                                         :operator 'and
                                         :identity-with-one-argument t))
                    :operator :call-next-method))

\endscreen!

\endsubSection%{Short Form of Define-method-combination}

\beginsubSection{Examples of the Long Form of Define-method-combination}

\screen!

;The default method-combination technique
(define-method-combination standard ()
        ((around (:around))
         (before (:before))
         (primary () :required t)
         (after (:after)))
  (make-method-call `(,@around
                      (multiple-value-prog2
                        ,(make-method-call before)
                        ,(make-method-call primary
                                           :operator :call-next-method)
                        ,(make-method-call (reverse after))))
                    :operator :call-next-method))

;A simple way to try several methods until one returns non-nil
(define-method-combination and ()
        ((methods () (:and)))
  (make-method-call methods :operator 'and))

;A more complete version of the preceding
(define-method-combination and 
        (&optional (order ':most-specific-first))
        ((around (:around))
         (primary () (:and)))
  ;; Process the order argument
  (case order
    (:most-specific-first)
    (:most-specific-last (setq primary (reverse primary)))
    (otherwise (method-combination-error "~S is an invalid order.~@
    :most-specific-first and :most-specific-last are the possible values."
                                         order)))
  ;; Must have a primary method
  (unless primary
    (method-combination-error "A primary method is required."))
  (make-method-call `(,@around
                      ,(make-method-call primary
                                         :operator 'and
                                         :identity-with-one-argument t))
                    :operator :call-next-method))

;The same thing, using the :order and :required keyword options
(define-method-combination and 
        (&optional (order ':most-specific-first))
        ((around (:around))
         (primary () (:and) :order order :required t))
  (make-method-call `(,@around
                      ,(make-method-call primary
                                         :operator 'and
                                         :identity-with-one-argument t))
                    :operator :call-next-method))

;This short-form call is behaviorally identical to the preceding
(define-method-combination and :identity-with-one-argument t)
 
;Order methods by positive integer qualifiers
;:around methods are disallowed to keep the example small
(define-method-combination example-method-combination ()
        ((methods positive-integer-qualifier-p))
  (make-method-call (stable-sort methods #'<
                       :key #'(lambda (method)
                                (first (method-qualifiers method))))))

(defun positive-integer-qualifier-p (method-qualifiers)
  (and (= (list-length method-qualifiers) 1)
       (typep (first method-qualifiers) '(integer 0 *))))

\endscreen!

\endsubSection%{Examples of the Long Form of Define-method-combination}


\endSection%{Declarative Method Combination}


\beginSection{Meta Objects}

\beginsubSection{Metaclasses}

The {\bit metaclass\/} of an object is the class of its class.  The
metaclass determines the form of inheritance used by its classes and the
representation of the instances of its classes.  The metaclass mechanism
can be used to provide particular forms of optimization or to tailor the
\CLOS\ for particular uses (such as the implementation of other object
languages---like Flavors, Smalltalk-80, and Loops).

Any new metaclass must define the structure of its instances, how their
storage is allocated, how their slots are accessed, and how slots and
methods are inherited.  The protocol for defining metaclasses will be
discussed in the document, ``The \CLOS\ Meta-Object Protocol''.  

\endsubSection

\beginsubSection{Standard Metaclasses}

The \CLOS\ provides a number of predefined metaclasses.  These
include the following: {\bf standard-class}, 
{\bf standard-type-class}, and {\bf structure-class}.

{\bf standard-class} is the default class of a class defined by {\bf defclass}. 

The class {\bf standard-type-class} is a metaclass of all the classes 
that correspond to the standard Common Lisp types specified in
{\it Common Lisp: The Language\/} by Guy L. Steele Jr. 
%except {\bf atom} and {\bf common}.  
These types are listed in Figure~1-1. 
%next sentence removed because it sounds bogus and doesn't add anything. -Sonya
%
%This metaclass allows the special kind of class 
%inheritance rules that are needed to handle the classes that 
%correspond to the standard Common Lisp types.
It is not allowed to make an instance of a standard type class using 
{\bf make-instance}, or to use a standard type class
as a superclass of a user-defined class. 

The class {\bf structure-class} is a subclass of {\bf standard-type-class}.  
All classes defined by means of {\bf defstruct} are instances of 
{\bf structure-class} or a subclass of {\bf structure-class}.

%The use of {\bf defstruct} implicitly defines a new class which is an
%instance of {\bf structure-class}.

%Instances of {\bf primitive-lisp-type-class} are classes that correspond
%to the basic Common Lisp types.  
%While all classes that correspond to the types
%listed in Figure}1-1 must be instances of either {\bf structure-class}
%or {\bf primitive-lisp-type-class}, no implementation is {\it required\/} to
%have any class that is an instance of {\bf primitive-lisp-type-class}.
%\endsubSection
% 
%\endSection

\endsubSection%{Standard Metaclasses} 

\beginsubSection{Standard Meta-Objects}

The \CLOS\ provides the predefined meta-objects called 
{\bf standard-method} and {\bf standard-generic-function}. 

{\bf standard-method} is the default class of a method defined by {\bf defmethod}
or {\bf defmethod-setf}.

{\bf standard-generic-function} is the default class of a generic function 
defined by {\bf defmethod}, {\bf defmethod-setf}, 
{\bf defgeneric-options}, or {\bf defgeneric-options-setf}.

The \CLOS\ also provides the standard method combination type, which is 
not implemented as a meta-object, but as a method. 

%Includes objects for classes, objects for methods, objects for generic functions.

%Use: efficiency in implementation; experimentation.

%Allows for variations in the representation of objects, the syntax of
%methods, the combination of methods.

%Can be used to provide tuning and optimization for a particular application.

\endsubSection%{Standard Meta-Objects} 

\endSection%{Meta-Objects}
\endChapter
\bye